home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-03
/
in_sort.zip
/
QUICKSRT.QB
< prev
Wrap
Text File
|
1991-05-01
|
2KB
|
64 lines
10 REM Written 8/28/85; by James Haley
20 REM non-recursive quicksort in basic
30 REM
40 OPTION BASE 1 ' all arrays start with 1, not zero
50 DEFINT A-Z ' make all variables integers
60 DIM VECTOR(10000) ' the array to be sorted
70 DIM STACK.LEFT(32) ' keeps track of what to sort
80 DIM STACK.RIGHT(32) ' keeps track of what to sort
90 REM
100 REM read in an array to sort
110 REM SORT.NUM contains the number of things to sort
120 REM
130 SORT.NUM = 0
140 INPUT "how many elements do you want to sort ";COUNT
150 FOR K = 1 TO COUNT
160 SORT.NUM = SORT.NUM + 1
170 VECTOR(SORT.NUM) = INT(RND*1000)
180 NEXT K
190 PRINT TIME$
200 REM
210 REM initialize the stack
220 REM
230 STACK.POINTER = 1
240 STACK.LEFT(STACK.POINTER) = 1 ' this is the first thing to sort
250 STACK.RIGHT(STACK.POINTER) = SORT.NUM ' this is the last thing to sort
260 REM
270 REM get the right and left limits of the array to sort from the stack
280 REM top of sort loop
290 REM
300 LEFT = STACK.LEFT(STACK.POINTER)
310 RIGHT = STACK.RIGHT(STACK.POINTER)
320 STACK.POINTER = STACK.POINTER - 1
330 REM
340 REM decide if this partition is sorted
350 REM
360 IF LEFT >= RIGHT THEN IF STACK.POINTER > 0 THEN GOTO 300 ELSE GOTO 570
370 REM
380 REM partition the array around the pivot
390 REM
400 I = LEFT
410 J = RIGHT + 1
420 PIVOT = VECTOR( LEFT )
430 J = J - 1 : IF VECTOR(J) > PIVOT GOTO 430
440 I = I + 1 : IF (VECTOR(I) < PIVOT) AND (I < RIGHT) GOTO 440
450 IF I < J THEN SWAP VECTOR(I), VECTOR(J) : GOTO 430
460 SWAP VECTOR(LEFT), VECTOR(J)
470 REM
480 REM set up stack for the sub-partitions
490 REM
500 STACK.POINTER = STACK.POINTER + 1 ' increment the stack
510 STACK.LEFT(STACK.POINTER) = J + 1 ' for the right side
520 STACK.RIGHT(STACK.POINTER) = RIGHT ' partition
530 STACK.POINTER = STACK.POINTER + 1 ' increment the stack
540 STACK.LEFT(STACK.POINTER) = LEFT ' for the left side
550 STACK.RIGHT(STACK.POINTER) = J - 1 ' partition
560 GOTO 300 ' go back and sort the next sub-partition
570 PRINT TIME$
580 REM
590 REM sort finished, print out the sorted array
600 REM
610 FOR K = 1 TO SORT.NUM
620 PRINT VECTOR(K);
630 NEXT K : PRINT